{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Combination With Bitwise AND Greater Than Zero"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestCombination"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #按位与结果大于零的最长组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>对数组&nbsp;<code>nums</code> 执行 <strong>按位与</strong> 相当于对数组&nbsp;<code>nums</code> 中的所有整数执行 <strong>按位与</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，对 <code>nums = [1, 5, 3]</code> 来说，按位与等于 <code>1 &amp; 5 &amp; 3 = 1</code> 。</li>\n",
    "\t<li>同样，对 <code>nums = [7]</code> 而言，按位与等于 <code>7</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个正整数数组 <code>candidates</code> 。计算 <code>candidates</code> 中的数字每种组合下 <strong>按位与</strong> 的结果。 <code>candidates</code> 中的每个数字在每种组合中只能使用 <strong>一次</strong> 。</p>\n",
    "\n",
    "<p>返回按位与结果大于 <code>0</code> 的 <strong>最长</strong> 组合的长度<em>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>candidates = [16,17,71,62,12,24,14]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>组合 [16,17,62,24] 的按位与结果是 16 &amp; 17 &amp; 62 &amp; 24 = 16 &gt; 0 。\n",
    "组合长度是 4 。\n",
    "可以证明不存在按位与结果大于 0 且长度大于 4 的组合。\n",
    "注意，符合长度最大的组合可能不止一种。\n",
    "例如，组合 [62,12,24,14] 的按位与结果是 62 &amp; 12 &amp; 24 &amp; 14 = 8 &gt; 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>candidates = [8,8]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>最长组合是 [8,8] ，按位与结果 8 &amp; 8 = 8 &gt; 0 。\n",
    "组合长度是 2 ，所以返回 2 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= candidates.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= candidates[i] &lt;= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-combination-with-bitwise-and-greater-than-zero](https://leetcode.cn/problems/largest-combination-with-bitwise-and-greater-than-zero/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-combination-with-bitwise-and-greater-than-zero](https://leetcode.cn/problems/largest-combination-with-bitwise-and-greater-than-zero/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[16,17,71,62,12,24,14]', '[8,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(30):\n",
    "            sum = 0\n",
    "            for x in candidates:\n",
    "                if x >> i & 1:\n",
    "                    sum += 1\n",
    "            ans = max(ans, sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        for num in candidates:\n",
    "            for i in range(32):\n",
    "                if num & 1 << i:\n",
    "                    cnt[i] += 1\n",
    "\n",
    "        return max(cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        cnts = [0] * 30\n",
    "        for c in candidates:\n",
    "            for i in range(30):\n",
    "                if c >> i & 1:\n",
    "                    cnts[i]+=1\n",
    "        return max(cnts)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        # 初始化候选数组和最长组合长度\n",
    "        c = candidates\n",
    "        n = len(c)\n",
    "        max_cnt = 0\n",
    "        \n",
    "        # 遍历所有可能的位\n",
    "        for i in range(0, 25):\n",
    "            # 生成具有该位为 1 的二进制数\n",
    "            bit = 1 << i\n",
    "            cnt = 0\n",
    "            \n",
    "            # 检查每个候选数字是否在该位上有 1\n",
    "            for ci in c:\n",
    "                if ci & bit != 0:\n",
    "                    cnt += 1\n",
    "            \n",
    "            # 更新最长组合长度\n",
    "            if cnt > max_cnt:\n",
    "                max_cnt = cnt\n",
    "                \n",
    "        return max_cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        cnt=[0]*32\n",
    "        for i in range(32):\n",
    "            for x in candidates:\n",
    "                cnt[i]+=(x&(1<<i))>0\n",
    "        return max(cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(28):\n",
    "            cnt=0\n",
    "            for x in candidates:\n",
    "                cnt+=(x&(1<<i))>0\n",
    "            ans=max(ans,cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        mask = 2 ** 24\n",
    "        answer = 0\n",
    "        while mask > 0:\n",
    "            count = 0\n",
    "            for index, candidate in enumerate(candidates):\n",
    "                if candidate & mask > 0:\n",
    "                    count += 1\n",
    "                candidates[index] = candidate % mask\n",
    "            answer = max(answer, count)\n",
    "            mask = mask >> 1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        for x in candidates:\n",
    "            for i in range(24):\n",
    "                if x >> i & 1:\n",
    "                    cnt[i] += 1\n",
    "        return max(cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        result = 0\n",
    "        for _ in range(24):\n",
    "            result = max(result, sum(map(lambda v: v & 1, candidates)))\n",
    "            for i in range(len(candidates)): candidates[i] >>= 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        return max(sum(x >> i & 1 for x in candidates) for i in range(24))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        res=0\n",
    "        n=len(candidates)\n",
    "        for i in range(0,31):\n",
    "            cnt=0\n",
    "            for x in candidates:\n",
    "                if x>>i&1:\n",
    "                    cnt+=1\n",
    "            res=max(res,cnt)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        maxv = max(candidates)\n",
    "        maxcnt = 0\n",
    "        while(maxv > 0):\n",
    "            maxv = maxv // 2\n",
    "            maxcnt += 1\n",
    "        result = 0\n",
    "        for i in range(maxcnt):\n",
    "            tmp = 0\n",
    "            for num in candidates:\n",
    "                tmp += (num // 2**i) % 2\n",
    "            result = max(result, tmp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        arr = [0]*32\n",
    "        for n in candidates:\n",
    "            for i in range(32):\n",
    "                if (1<<i)&n:\n",
    "                    arr[i]+=1\n",
    "        return max(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        res=0\n",
    "        for i in range(31,-1,-1):\n",
    "            count=0\n",
    "            for num in candidates:\n",
    "                n=(num>>i)&1\n",
    "                if n==1:\n",
    "                    count+=1\n",
    "            res=max(count,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        sumv = [0 for i in range(0, 25)]\n",
    "        for x in candidates:\n",
    "            for j in range(0, 30):\n",
    "                if x >> j ==0:\n",
    "                    break\n",
    "                if x >> j & 1 == 1:\n",
    "                    sumv[j] += 1\n",
    "        return max(sumv)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        cnt = [0] * 24          # cnt[i]: 二进制第i位上1的数目\n",
    "        \n",
    "        for num in candidates:\n",
    "            i = 0\n",
    "            while num:\n",
    "                if num & 1:     # 当前第i位为1\n",
    "                    cnt[i] += 1\n",
    "                num >>= 1\n",
    "                i += 1\n",
    "        \n",
    "        return max(cnt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        return max(sum(num >> i & 1 for num in candidates) for i in range(24))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        MAX_BIT = 24\n",
    "        count = [0] * 24\n",
    "        for i in candidates:\n",
    "            for _ in range(MAX_BIT):\n",
    "                count[_] += i & 0x01\n",
    "                i >>= 1\n",
    "                if i == 0:\n",
    "                    break\n",
    "        return max(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        max_res = 0\n",
    "        for bit in range(0,31):\n",
    "            cur = 0\n",
    "            for num in candidates:\n",
    "                if (num>>bit)&1:\n",
    "                    cur+=1\n",
    "            max_res = max(max_res, cur)\n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        high_bit = max(candidates).bit_length()\n",
    "        ans = -1\n",
    "        for i in range(high_bit-1, -1,-1):\n",
    "            cnt = 0\n",
    "            for x in candidates:\n",
    "                cnt += (x >> i) & 1\n",
    "            ans = max(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        maxv = max(candidates)\n",
    "        maxcnt = 0\n",
    "        while(maxv > 0):\n",
    "            maxv = maxv // 2\n",
    "            maxcnt += 1\n",
    "        result = 0\n",
    "        for i in range(maxcnt):\n",
    "            tmp = 0\n",
    "            for num in candidates:\n",
    "                tmp += (num // 2**i) % 2\n",
    "            result = max(result, tmp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        cnt = [0] * 32\n",
    "        for c in candidates:\n",
    "            for i in range(31):\n",
    "                if (c >> i) & 1:\n",
    "                    cnt[i] += 1\n",
    "        return max(cnt)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        n=len(candidates)\n",
    "        #二进制不会超过32位\n",
    "        cnt = [0]*32\n",
    "        max_ans=0\n",
    "        for i in candidates:\n",
    "            for j in range(32):\n",
    "                if ((1<<j)&i) >0:\n",
    "                    cnt[j]+=1\n",
    "        for i in range(32):\n",
    "            max_ans=max(max_ans,cnt[i])\n",
    "        return max_ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        maxv = max(candidates)\n",
    "        maxcnt = 0\n",
    "        while(maxv > 0):\n",
    "            maxv = maxv // 2\n",
    "            maxcnt += 1\n",
    "        result = 0\n",
    "        for i in range(maxcnt):\n",
    "            tmp = 0\n",
    "            for num in candidates:\n",
    "                tmp += (num // 2**i) % 2\n",
    "            result = max(result, tmp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        def maxlen(k):\n",
    "            res = 0\n",
    "            for num in candidates:\n",
    "                if num & (1 << k):\n",
    "                    res += 1\n",
    "            return res\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(24):\n",
    "            res = max(res, maxlen(i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        has, n = [0] * (len(bin(max(candidates))) - 2), len(candidates)\n",
    "        for i in candidates:\n",
    "            tep, ni = 0, i\n",
    "            while ni: has[tep], ni, tep = has[tep] + ni % 2, ni // 2, tep + 1\n",
    "        return max(has)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        res = 0\n",
    "\n",
    "        def maxlen(i):\n",
    "            cnt = 0\n",
    "            for num in candidates:\n",
    "                if num & (1 << i):\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "        \n",
    "\n",
    "        for i in range(24):\n",
    "            res = max(res, maxlen(i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        # 这玩意找的是子序列，只需要统计某一位值的最多个数就行了，10**7最多不会超过30位的\n",
    "        ans = 0\n",
    "        for d in range(30):\n",
    "            cnt = 0\n",
    "            for c in candidates:\n",
    "                if c >> d & 1:\n",
    "                    cnt += 1\n",
    "            ans = max(cnt, ans)\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        for num in candidates:\n",
    "            idx = 0\n",
    "            while num > 0:\n",
    "                if num & 1 == 1:\n",
    "                    cnt[idx] += 1\n",
    "                num >>= 1\n",
    "                idx += 1\n",
    "        ans = max(cnt.values())\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(25):\n",
    "            cnt=0\n",
    "            for x in candidates:\n",
    "                cnt+=(x&(1<<i))>0\n",
    "            ans=max(ans,cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        ans = 0\n",
    "        pre = [0]*32\n",
    "        for num in candidates:\n",
    "            for j in range(32):\n",
    "                if num & (1<<j):\n",
    "                    pre[j] += 1\n",
    "        return max(pre)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        return max(sum(n & (1 << i) > 0 for n in candidates) for i in range(24))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        bits = [0] * 31\n",
    "        for i in range(31):\n",
    "            for x in candidates:\n",
    "                if x & 1 << i:\n",
    "                    bits[i] += 1\n",
    "        return max(bits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(24):\n",
    "            temp = sum([num >> i & 1 for num in candidates])\n",
    "            ans = max(temp, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        n = len(bin(10**7)[2:])\n",
    "        res = 1\n",
    "        for i in range(n):\n",
    "            tmp = 0\n",
    "            for c in candidates:\n",
    "                if c & (1 << i):\n",
    "                    tmp += 1\n",
    "            res = max(res, tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        n=len(candidates)\n",
    "        #二进制不会超过32位\n",
    "        cnt = [0]*32\n",
    "        max_ans=0\n",
    "        for i in candidates:\n",
    "            for j in range(32):\n",
    "                if ((1<<j)&i) >0:\n",
    "                    cnt[j]+=1\n",
    "        for i in range(32):\n",
    "            max_ans=max(max_ans,cnt[i])\n",
    "        return max_ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestCombination(self, candidates: List[int]) -> int:\n",
    "        ans = -inf\n",
    "        for i in range(24):\n",
    "            res = 0\n",
    "            for candidate in candidates:\n",
    "                if (candidate >> i) & 1:\n",
    "                    res += 1\n",
    "            ans = max(ans, res)\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
